/**
 * @ClassName MinWeightTriangulation
 * @Description TODO
 * @Author Quentin_zyj
 * @Date 2021/11/2 14:34
 */
public class MinWeightTriangulation {

    public static void minWeightTriangulation(int n, int[][] t, int[][] s, int w[][]) {
        for (int i = 1; i <= n; i++) {
            t[i][i] = 0;
        }
        for (int r = 2; r <= n; r++) {
            for (int i = 1; i <= n - r + 1; i++) {
                int j = i + r - 1;
                t[i][j] = t[i][i] + t[i + 1][j] + w[i - 1][i] + w[i][j] + w[j][i];
                s[i][j] = i;
                for (int k = i + 1; k < j; k++) {
                    int u = t[i][k] + t[k + 1][j] + w[i - 1][k] + w[k][j] + w[j][i - 1];
                    if (u < t[i][j]) {
                        t[i][j] = u;
                        s[i][j] = k;
                    }
                }
            }
        }
    }
}
